package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-05-22-21:38
 */
public class QuickSort {
    /*
    * 快速排序是对冒泡排序的一种改进，基本思想是通过一趟排序将要排序的数据分割成两部分，其中独立的一部分数据比另一部分独立的数据都要小，
    * 然后按照这个方法对这两部分数据分别再次进行快速排序，整个排序的过程都可以进行递归，以此达到真个数据有序。
    *
    * */
    public static void sort(int[] arr){
        sort(arr,0,arr.length-1);
    }
    public static void sort(int[] arr,int leftBound,int rightBound){
        if(leftBound>=rightBound) return;
        int mid = quick(arr, leftBound, rightBound);
        sort(arr,leftBound,mid-1);
        sort(arr,mid+1,rightBound);

    }
    public static int quick(int[] arr,int leftBound,int rightBound){
        int postion=rightBound;
        int left=leftBound;
        int right=rightBound-1;
        while (left<=right){
            while (left<=right&&arr[left]<=arr[postion])left++;
            while (left<=right&&arr[right]>arr[postion])right--;
            if(left<right){
                Swap.swap(arr,left,right);
            }
        }
        Swap.swap(arr,left,postion);
        return left;

    }

    public static void main(String[] args) {
        int[] arr={3,6,7,8,1,4,2,9,10,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
